package com.ys.p1.method;

/**
 * @author CodeYang
 * @Description 判断1到100之间的素数
 * @Date 2020/12/8 20:31
 */


public class 判断1到100之间的素数 {


    public static void main(String[] args) {
        for (int i = 1; i <= 100; i++) {
            if (isPrime(i)) {
                System.out.println("是素数:" + i);
            }
        }
    }

    /**
     * 判断是不是素数
     * 只能被1和它本身整除
     *1.质数
     * 定义：质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
     *
     * 2.质数的范围
     * 大于2的偶数（num），它等于一个数（i）与另一个数的和（num - i）。所以，i 与（num - i）的范围
     * 是质数的范围。
     *
     * 3.质数的判断
     * 判断 i 与（num - i）是不是质数，可以一个函数专门解决
     * @param num
     * @return
     */
    static boolean isPrime(int num) {
        boolean flag = true;
        if (1 == num) {
            return false;
        }
//       1: 最原始写法,效率最低,需要遍历从2 到 num 之间的所有数来进行判断
//        for (int i = 2; i < num; i++) {
//       2: 第二种写法
//        从 i 开始遍历，判断 i 与 （num - i）是不是质数，那么当 i 大于 （num / 2）时，遍历此时无意义。
//        例如： 偶数18 先判断 3 与 15，接着 5 与 13 ，（假设·继续）接着 7 与 11， 接着 9 和 9 ，
//        接着 11 与 7 此时就无意义了。两个质数最大都为原数的一半，例如 6 = 3 + 3， 10 = 5 + 5.
//        for (int i = 2; i < num/2; i++) {
//       3: 第三种写法:判断素数:n能否被2~√n整除
//        (i = 2; i <num && num % i; i++)， 从 i 遍历 到 num 太浪费时间。 如果 i 是偶数，偶数如果是质数的因数，那么 2 必定是，所以可以 把偶数排除。
//        换个说法，原数是10000，
//        如果 2 不是它的因数，则 5000也不是它的因数，那么在5001 ~ 10000也肯定找不到它的因数，
//        同样，3不是他的因数，那么3333也不是他的因数，则3334 ~ 5000 里也不存在它的因数。
//        于是，4 与 2500 ，5与 2000等等
//        直到，10000^0.5 = 100 是，此时100 ~ 10000以后的数都不需要找因数，只用看2 到 100.
//        所以，从 2遍历到原数的开方，就足够。
//   因为一个数 必定是一个 大数*小数 =这个数
        // 且 a =b *c  极限情况就是 b==c 所以只需要判断开方后的 2- sort(a)的范围内有没有 可以被整除的非质数
       for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

}
